package leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by Ghost on 2014/11/18 0018.
 */
public class Binary_Tree_Level_Order_Traversal_II {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        LinkedList<List<Integer>> rst = new LinkedList<List<Integer>>();
        if(root==null)
            return rst;
        queue.add(root);
        int count;
        while(!queue.isEmpty()){
            count = queue.size();
            List<Integer> list = new LinkedList<Integer>();
            while(count>0){
                TreeNode cur = queue.poll();
                if(cur.left!=null)
                    queue.add(cur.left);
                if(cur.right!=null)
                    queue.add(cur.right);
                count--;
                list.add(cur.val);
            }
            rst.add(list);
        }
        LinkedList<List<Integer>> rst2 = new LinkedList<List<Integer>>();
        while(!rst.isEmpty()){
            List<Integer> tail = rst.pollLast();
            rst2.add(tail);
        }
        return rst2;
    }
    public static void main(String[] args){
        Binary_Tree_Level_Order_Traversal_II binary_tree_level_order_traversal_ii = new Binary_Tree_Level_Order_Traversal_II();
        TreeNode root = new TreeNode(1);
        /*root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.left.right = new TreeNode(5);*/

        List<List<Integer>> list = binary_tree_level_order_traversal_ii.levelOrderBottom(null);

        for(List<Integer> subList:list){
            for(Integer i:subList){
                System.out.print(" " + i);
            }
            System.out.println();
        }
    }
}
